For some linear block codes, one may design a joint Maximum Likelihood (ML) channel-code detector. However, these detectors tend to be very complicated, even for relatively simple (and ultimately weak) codes. In some special cases, one may obtain reasonable performance by completely separating the channel detector 12 from the code decoder 14, as shown in the system 10 in FIG. 1.
A system such as that shown in FIG. 1 could use, for example, Reed-Solomon (RS) Error Correction Code (ECC). RS codes have implementation-efficient algebraic decoders that can decode up to (or even beyond) half the minimum distance of the code. Nevertheless, the performance of such a detector 10 is much worse compared to what can be achieved by joint ML channel-code decoders.
In some instances, the error correction capability of linear block code might not be sufficient to meet the demands of certain applications. In effect, such poor error correction capability precludes one from running a linear block code decoder separately from the channel detector. FIG. 2 shows a block diagram for a system 20 employing an outer RS ECC encoder 22 in concatenation with an inner Cyclic Redundancy Code (CRC) encoder 24 that is commonly used in magnetic recording channels.
In magnetic recording applications, the outer RS ECC code is designed to cover a relatively large block of data (e.g., 512 bytes). On the contrary, the inner ECC (n, k) code has a smaller block length. For this reason, the RS ECC output is partitioned into a plurality of blocks, having length k. Each block is then encoded into n-bit long CRC code words. CRC code words are concatenated together and transmitted over a noisy channel (e.g., a channel that introduces non-negligible random and/or Gaussian noise into a transmission).
FIG. 3 shows an exemplary decoder 30 for a magnetic recording system, matched to the encoder system 20 in FIG. 2. Decoder 30 generally includes a Viterbi detector 32, a post processor 34, and a RS ECC decoder 36. In the decoder architecture 30 of FIG. 3, the inner CRC code is decoded with Post Processor circuit (“PP detector”) 34. PP detector 34 assumes the presence of a primary channel detector (e.g., Viterbi detector 32). Thereafter, two further simplifying assumptions are typically made to enable PP-based implementations.
First, PP-based implementations generally assume that all errors following the Viterbi detector come from the list of dominant error events, designated herein as E. Different channels may have different lists of dominant error events, and therefore, the contents of E are generally determined before use. For instance, in certain magnetic recording channel applications, E can be {+, +−, +−+, +0+, +−+−, +−+−+}. Of course, more error events can be added to the list, but there is a very practical trade-off between performance (e.g., processing speed) and complexity (e.g., number of error events in E). Secondly, PP-based approaches generally assume that there are at most M errors per CRC codeword.
These assumptions may lead to performance degradation. For instance, if the true error event corrupting some CRC codeword is not an element of E, or if there is a composite error event consisting of more than M (e.g., some combination of two or more events within E), PP architectures are generally not going to be able to find the transmitted codeword. To make things worse, a PP architecture may converge to an incorrect CRC codeword (e.g., a codeword other than the one that was transmitted) or erroneously correct the CRC codeword, which may actually increase the number of errors present in the CRC codeword following Viterbi detection. Caution should be taken to minimize occurrences of erroneous correction.
Before post processing can be performed, Viterbi detector 32 obtains a most likely path through the trellis based on the received samples. The Viterbi detector 32 generally does not take any CRC constraints into account, and as a result, the PP 34 is used to improve upon the Viterbi detector results by searching for the best path through the trellis which satisfies the CRC constraint(s).
In CRC code theory, it is helpful to represent CRC code words as polynomials over some finite field, F. With each codeword c=(c0, c1, . . . , cn−1) (i.e., a string of symbols from field F), we can associate a polynomial c(x) over F of degree less than n, given by
      c    ⁡          (      x      )        =            ∑              i        =        0                    n        -        1              ⁢                  ⁢                  c        i            ⁢                        x          i                .            Equivalently, every polynomial over field F of degree less than n can be represented as a string of n symbols, where the ith symbol coincides with the coefficient of xi, i=0, 1, . . . , n−1. CRC code may be specified in terms of a generator polynomial g(x). The codeword c(x) is said to belong to the codeword space of the CRC(n,k) code defined by the generating polynomial g(x) if and only if g(x) divides c(x) without a remainder (i.e., Rem(c(x),g(x))=0, where 0 stands for a zero polynomial). The invention will be explained often herein with reference to binary CRC codes (i.e., where F=GF(2)); however, it should be apparent to those skilled in art that the inventive concepts described herein can be easily applied to or extended to codes over higher order fields. It is also convenient to represent members of E in polynomial notation as well, e.g. E={1, 1+x, 1+x+x2, 1+x2, 1+x+x2+x3, 1+x+x2+x3+x4}.
As discussed above, the concatenation of outer RS ECC code with inner CRC code has been widely used in magnetic recording systems in recent years. Most popular system architectures employ shortened (61, 60) single parity check (SPC) cyclic binary code, with a generator polynomial given by g(x)=1+x as the inner ECC (also see, e.g., U.S. Pat. Nos. 6,526,530 and 6,456,208, the relevant portions of which are incorporated herein by reference). Some other popular choices for inner ECC are those generated by the polynomials g(x)=1+x2, g(x)=1+x+x3, and g(x)=1+x+x2+x4, and having a block length under 100-120 bits. The codes described above have very small minimum distances, and as a result, are not very good at error correction. For instance, SPC code has dmin=2, and as a result, it is unable to correct a single error. Consequently, on the decoding side, the error detection properties of inner ECC codes are generally used in conjunction with channel metrics to perform error correction.
A Maximum Likelihood Distance Penalty (MLDP) may be assigned to (or calculated for) the paths corresponding to a single dominant error event. Referring now to FIG. 3, let v(x) denote the plurality of Viterbi decisions (i.e., a set or series of possible sequences determined by Viterbi decoder 32 for data received from a channel). For each location of the CRC codeword, PP 34 forms an alternative path to the output of Viterbi decoder 32 by inserting one of the dominant error events from the list E into the Viterbi decision bit stream. In polynomial notation, the alternative path corresponding to the dominant error event e at some bit position l can be written as v(x)+e(x)xl. For each alternative path (note that n*|E| such paths can be formed for a single CRC codeword; each of n locations can have |E| alternative paths), PP 34 assigns a measure of likelihood by computing the MLDP), which is given by the Path Metric (PM) difference between the alternative path and Viterbi decision bit stream, MLDP(e)=PM(v(x)+e(x)xl)−PM(v(x)). Since Viterbi detector 32 outputs the most likely path through the trellis (i.e., the path with the smallest PM), MLDP(e) is always greater than or equal to 0.
However, if e is a composite error event (e.g., e=e1+e2+ . . . +ek, where e consists of several non-overlapping dominant error events), then
                    M        ⁢                                  ⁢        L        ⁢                                  ⁢        D        ⁢                                  ⁢        P        ⁢                                  ⁢                  (          e          )                    =                        ∑                      i            =            1                    k                ⁢                  M          ⁢                                          ⁢          L          ⁢                                          ⁢          D          ⁢                                          ⁢                      P            ⁡                          (                              e                i                            )                                            ,    ⁢        where MLDP(ei) is the composite penalty of the individual component error events, i=1, 2, . . . , k. If the component error events overlap, or if the number of bits between two component error events (from the end of one to the beginning of the next) is less than channel memory, the above formula does not apply. Consequently, MLDP for overlapped error events are difficult to calculate. Therefore, even if such error events are selected by a PP algorithm, they should be disabled in the correction block if their MLDP can not be accurately calculated.
An MLDP can be computed based on the likelihood measure used by Viterbi detector 32. Alternatively, it is possible to assign likelihoods using a more computation-intensive likelihood function (e.g. one taking data dependent noise into account; see, e.g., U.S. patent application Ser. Nos. 10/208,312, filed on Jul. 29, 2002, and 10/689,660, filed on Oct. 31, 2003, the relevant portions of which are incorporated herein by reference). If the latter is used, then the formula MLDP(v(x)+e(x)) is not necessarily greater than or equal to zero, since v(x) is not necessarily optimal with respect to the data dependent likelihood function.
Once the penalties corresponding to various error events have been computed, PP 34 searches for an alternative path corresponding to a combination of at most M error events that (1) bring v(x) into the codeword space of the inner ECC and (2) has smallest MLDP among all such paths. Herein, the term “v(x)” is used to denote the plurality of Viterbi decisions, as well as a subset of these decisions corresponding to a particular CRC codeword. Where applicable, the context of any given use of “v(x)” herein may impart a particular meaning to those skilled in the art.
Let v(x) be the received CRC codeword. If r(x)=Rem(v(x), g(x))=0, then either v(x) equals the transmitted CRC codeword, or r(x) is corrupted by an error event that cannot be detected by CRC. In either case, PP 34 does not make any corrections. On the other hand, if Rem(v(x),g(x))=r(x) does not equal a zero polynomial, then v(x) is corrupted by some error pattern which can be identified using the methodology of the PP detector 34 (assuming that all of the assumptions made by PP detector 34 hold true). FIG. 4 depicts circuitry 40 for carrying out polynomial division which is commonly used to compute remainders.
As PP 34 processes alternative paths, attention tends to be directed to those error events that bring v(x) into the codeword space, or the paths for which Rem(v(x)+e(x), g(x))=0, or more generally, Rem(v(x)+e1(x)+e1(x)+ . . . +ek(x), g(x))=0. Methods for computing a remainder corresponding to a dominant error event e are discussed below. However, it is worth noting that one does not necessarily need to use polynomial division logic to compute the remainders corresponding to composite error events. Once the remainder of each component error event is known, one can utilize linearity to obtain the following identity: Rem(v(x)+e1(x)+e2(x)+ . . . +ek(x), g(x))=Rem(v(x), g(x))+Rem(e1(x), g(x))+Rem(e2(x), g(x))+ . . . +Rem(ek(x), g(x)). Thus, the remainder corresponding to a composite error event e can be obtained as a sum over field F of the remainders of the component error events.
To summarize, the operation of PP 34 includes the following steps for each received CRC codeword, v(x):                1. Compute the remainder r(x)=Rem(v(x), g(x)). If r(x)=0, then the Viterbi decoder has output either a codeword with no errors or a codeword that cannot be corrected using PP 34; otherwise go to step 2.        2. Form a set of alternative paths P, where each path p in P corresponds to some dominant error event e(x) in E, i.e. p(x)=v(x)+e(x). For each such path, compute MLDP(e) and Rem(e(x), g(x)).        3. Extend the collection P by possibly adding paths corresponding to composite error events, whose MLDP and remainders can be computed based on similar quantities for individual components of e(x).        4. Search for the path p(x) in P corresponding to an error event or a combination of error events satisfying:                    a. Rem(p(x), g(x))=0; and            b. Among the p(x) satisfying 4(a), choose the one with the smallest MLDP:                        
  p  =            min                        p          ′                ⁢        ε        ⁢                                  ⁢        P              ⁢                  (                  M          ⁢                                          ⁢          L          ⁢                                          ⁢          D          ⁢                                          ⁢          P          ⁢                                          ⁢                      (                          p              ′                        )                          )            .                      5. If step 4 produces a non-trivial candidate p(x), then correct the codeword using candidate p(x); otherwise decoder failure is declared.        
The size of P is proportional to the cardinality of E, the length of the CRC code, n, and the value of parameter M, which bounds maximum number of error events which can be corrected per sector. It can be seen that the cardinality of P gets to be very large even for moderate values of |E|, n, and M. To reduce the complexity of the operations of PP 34, it is common to reduce the size of P following step 2 by keeping only the N best paths or N most likely errors with respect to MLDP prior to moving on to step 3. However, even for relatively small values of N, the number of paths to be considered in step 4 can be very large. For example, consider the case where N=10 and M=4, where the cardinality of P following step 3 is
            (                                    10                                                1                              )        +          (                                    10                                                2                              )        +          (                                    10                                                3                              )        +          (                                    10                                                4                              )        =  394.
In the past, the choice of CRC codes which can be implemented in practice were limited to codes having relatively small block length n (generally, under 120 bits), due to the complexity of having to search through a large number of paths. As n grows, the parameter M also generally increases, since the probability of having multiple error events in a single CRC codeword increases with codeword size. However, as previously discussed, the complexity of a PP-based architecture is ultimately related to the choice of parameter M. On the other hand, short CRC codes are not optimal either due to (i) the relatively low error detection and correction capability of these codes and/or (ii) the high code rate penalty they inflict on the communication system.
FIG. 5 shows a conventional process 50 for checking and correcting errors in data blocks transmitted over a channel using CRC code. First, a code word or code block is received in step 52. The channel typically introduces some noise into the transmitted code, and as a result, the received code word or block may be considered “noisy.” Thereafter, in step 54, the received code words are decoded, then in step 56, the received code word is divided by a generator polynomial g(x) to determine the remainder r(x)=Rem(v(x),g(x))(g(x) is generally known to the receiver as well as the transmitter, and does not change from codeword to codeword or sector to sector). Step 56 is essentially the error checking part of the process 50. A processing decision is made in step 60, depending on whether a zero remainder is obtained form the code word division step 56. If a zero remainder is obtained, then one may conclude that there is no error in the transmitted code word in result 62, and the decoded code word obtained in step 54 may be output.
On the other hand, if r(x) does not equal a zero polynomial, then there is an error in v(x), and the received code word has to be corrected. The corrected code words (generally corresponding to the paths p(x) in alternative path set P above) are then divided by the generator polynomial in step 66, similar to the process in step 56. The paths are searched for those that provide a zero remainder, then a decision is made on further processing of the corrected code word(s) in step 70, depending on whether any paths having a zero polynomial are found in step 68. If not, then the received code word is not corrected, and decoding failure is declared (see result 72). If one or more paths having a zero polynomial are obtained, then the path having the smallest penalty is identified (see decision 80). The corrected code word for which a non-trivial path having the smallest penalty is output as the decoded code word (see result 82). However, if such a non-trivial candidate path is not identified, then the received code word is not corrected and decoding failure is declared (see result 84).